/**
 * 经典问题
 * 问能否将给定数组元素分为两半，使得和值相等
 */
using vi = vector<int>;
vi D;
int N;
int Limit;

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        N = nums.size();
        Limit = accumulate(nums.begin(), nums.end(), 0);
        if(Limit & 1) return false;

        D.assign(Limit + 1, 0);
        D[0] = 1;
        for(auto i : nums){
            for(int v=Limit;v>=i;--v){
                D[v] |= D[v - i];
            }
        }
        return D[Limit/2];
    }
};
